Tag:隨意刷-未寫過的

Source:

995. Minimum Number of K Consecutive Bit Flips

1.題意:

In: nums,k
Out: 最小Flip次數

由0與1所組成的nums;
k為連續幾bit做一次Flip;
目的為藉由Flip，使得最後nums是皆為1的array。
要連續k bit(s)做Flip才是Flip，無法則視為無解(return -1)。
如果存在無法經由Flip使得最後nums是皆為1的array的情況，則無解(return -1)。

2.思路:

作法:

flipped 因之前的操作而使得目前為已Flip(1)，或是未Flip(0);
isFlipped 記錄每個位置是否被Flip;

☆ 什麼情況進行Flip?

情況1: 原arr記錄值為0，還沒被Flip
Or
情況2: 原arr記錄值為1，但被Flip(所以值為0，需再次被Flip)

3.程式碼:

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        flipped = 0
        isFlipped = [0]*len(nums)
        res = 0
        for i in range(len(nums)):
            if i>=k:
                flipped^=isFlipped[i-k]
            if nums[i]^flipped==0:
                if i+k>len(nums):
                    return (-1)
                flipped^=1
                isFlipped[i]=1
                res+=1
        return res        

Result:

Level:Hard

Note:

Hard 在於提升效能!
O(n^2)會TLE(Time Limit Exceeded).

• Ex:

  class Solution:
      def minKBitFlips(self, nums: List[int], k: int) -> int:
          flag = 0
          ans = 0
          for i in range(len(nums)):
              if nums[i] == 0:
                  cnt = 0
                  while (i+cnt)<len(nums):
                      if nums[i+cnt]==1:
                          nums[i+cnt]=0
                      else:
                          nums[i+cnt]=1
                      cnt+=1
                      if cnt>=k:
                          break
                  #print("cnt:",cnt)
                  if cnt!=k:
                      flag = 1
                  else:
                      ans+=1
              #print(nums)
  
          if sum(nums)!=len(nums) or flag==1:
              return (-1)
          return ans            
  

  

補充

• XOR